package ch5.part6;

/**
 * 无序数组排序后的最大相邻差
 * 利用桶排序的思路实现
 * 时间复杂度：O(n) = n
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class MaxSortedDistance {

    private static int getMaxSortedDistance(int[] array) {
        // 1.确定数列偏移量和最大最小值
        int max = array[0], min = array[0];
        for (int i = 1, len = array.length; i < len; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }
        int d = max - min;
        if (d == 0) {
            return 0;
        }

        // 2.初始化桶
        int bucketNum = array.length;
        Bucket[] buckets = new Bucket[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = new Bucket();
        }

        // 3.构建桶，记录每个桶里面的最大值和最小值
        for (int value : array) {
            int index = (value - min) * (bucketNum - 1) / d;
            if (buckets[index].min == null || buckets[index].min > value) {
                buckets[index].min = value;
            }
            if (buckets[index].max == null || buckets[index].max < value) {
                buckets[index].max = value;
            }
        }

        // 4.遍历桶，找最大差值
        int leftMax = buckets[0].max;
        int maxDistance = 0;
        for (int i = 1; i < bucketNum; i++) {
            if (buckets[i].min == null) {
                continue;
            }
            if (buckets[i].min - leftMax > maxDistance) {
                maxDistance = buckets[i].min - leftMax;
            }
            leftMax = buckets[i].max;
        }
        return maxDistance;
    }

    private static class Bucket {
        private Integer max;
        private Integer min;
    }

    public static void main(String[] args) {

        int[] array = {2, 6, 3, 4, 5, 10, 9};
        System.out.println(getMaxSortedDistance(array));

    }


}
